package string.滑动窗口;

import java.util.SimpleTimeZone;

/**
 * @Author kaho
 * @create 2020/11/30
 */
public class _567_字符串的排列 {

    /**
     * 给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。
     * <p>
     * 换句话说，第一个字符串的排列之一是第二个字符串的子串。
     * <p>
     * 示例1:
     * <p>
     * 输入: s1 = "ab" s2 = "eidbaooo"
     * 输出: True
     * 解释: s2 包含 s1 的排列之一 ("ba").
     *  
     * <p>
     * 示例2:
     * <p>
     * 输入: s1= "ab" s2 = "eidboaoo"
     * 输出: False
     * <p>
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/permutation-in-string
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     *
     * @param s1
     * @param s2
     * @return
     */
    public static boolean checkInclusion1(String s1, String s2) {
        int len1 = s1.length(), len2 = s2.length();
        if (len1 > len2) {
            return false;
        }
        int[] ch_count1 = new int[128], ch_count2 = new int[128];
        for (int i = 0; i < len1; ++i) {
            ++ch_count1[s1.charAt(i)];
            ++ch_count2[s2.charAt(i)];
        }
        for (int i = len1; i < len2; ++i) {
            if (isEqual(ch_count1, ch_count2)) {
                return true;
            }
            --ch_count2[s2.charAt(i - len1)];
            ++ch_count2[s2.charAt(i)];
        }
        return isEqual(ch_count1, ch_count2);
    }

    private static boolean isEqual(int[] ch_count1, int[] ch_count2) {
        for (int i = 0; i < ch_count1.length; ++i) {
            if (ch_count1[i] != ch_count2[i]) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        boolean b = checkInclusion("ab", "eidbaooo");
    }

    public static boolean checkInclusion(String s1, String s2) {
        int[] c1 = new int[128];
        int[] c2 = new int[128];
        for (int i = 0; i < s1.length(); i++) {
            c1[s1.charAt(i)]++;
            c2[s2.charAt(i)]++;
        }
        for (int i = s1.length(); i < s2.length(); i++) {
            if(isEqual(c1,c2)){
                return true;
            }
            c2[i- s1.length()]--;
            c2[i]++;
        }
        return isEqual(c1,c2);
    }

}
